\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}
\title{Project Report for \\Formal Languages and Compilers\\\begin{normalsize}(compiler extension for pointers and records)\end{normalsize}}
\author{Loris Dal Lago\\M. 139428}
\date{\today}

\def \CCC {Crème CAraMeL }
\def \C {C }
\def \HAT {\textasciicircum}

\begin{document}
\maketitle

\tableofcontents
\newpage

\section{Introduction}
My project is about extending the \CCC compiler in order to allow pointers and records to be used by the user programmer.
\\
Here it follows a preliminary section to expound some initial considerations on the work, then the two parts of pointers and records are treated and finally some final remarks.
\\
\\
The examples that show the new functionalities of \CCC are provided together with this report. If something is not clear here in the report, please try to get a look to those examples, that in most cases are self-explanatory. However they are provided with a file that helps you to navigate among them and gives a brief description and the output of each example.
\\
Not all the use case examples are compiling wrt \CCC, some of them are just examples of things that cannot be done in our language.
\\
\\
For almost every [sound] modification of the original compiler there is at least one comment in the code. My comments can be easily identified by a common pattern like:
\\
\begin{center}
(* LDL: $\ll$comment$\gg$ *)
\end{center}

.\\and they describe quite well the (sometimes trivial) actions on the code. So if something seems to be vaguely explained in this report, please try to give a peep at the code and see if the comments are more explanatory.
\\
\\
Before starting to implement the code for extending the compiler it was done a code analysis both for the pointer part and for the record part.
After that the two cases were dealt separately one after the other.




\section{Extension to Pointers}
Here it is described how I decided to extend the syntax and the semantics of \CCC in order to allow l-values to be assigned to variables (i.e. identifiers) and used to reference stack position offsets.




\subsection{Analysis of the problem}
Here I expound the problem and the basic implications over the syntax and the semantics, highlighting what I did and what I didn't and for what reason.
\\
\\
So the first question/issue I got was understanding what a pointer might mean in \CCC. A pointer is basically an offset on the stack. Hereafter the two terms are used as synonymous.
\\
So an instruction like: 
\[px := @x\]
shall evaluate $x$ as an offset and return its value on the stack (we call it a reference operation over variable $x$).
\\
Conversely,
  \begin{center}
  $x := $\HAT$px$;
  \end{center}
shall take the offset held by $px$ and move on the stack to the position it refers (we call it a dereference operation over variable $px$).
\\
\\
Before leaving the land for the sea, I listed all the behaviors that I wanted \CCC to get from the introduction of pointers, and here I recopy them:
\begin{itemize}
  \item I allow direct pointer assignment like
  \begin{center}
  $px$ = 0x($1$)  
  \end{center}
  to mean the offset 1 to be assigned to variable $px$. There will not be any means to know whether the offset belongs to a variable declaration or not; just as in other languages like \C it is up to the user programmer to ensure this.
  \\\textit{NULL} can be used to invalidate a pointer.
  \\Pointers are always checked to be valid before using them. This means that invalid dereferencing operations are eliminated whenever found (this part gave me some hitches in the implementation phase). This procedure is taken and handled at run-time, since the requirement that pointers be initialized to some address in the stack before they are used (i.e. dereferenced), cannot be described by a context-free grammar (like the one for \CCC), so we shall defer the check at run-time.
  
  \item the \HAT \hspace{2pt} symbol has to be used both for pointer variables declaration and for pointer dereferencing. It raises no parsing conflict since they are used in structurally different sections of the \CCC code.
  
  \item strange combinations of pointers operations are not allowed in \CCC, only consecutive dereferencings. So
  \begin{center}
  \HAT$@x$;
  \\$@$\HAT$px$;
  \\$@@x$;
  \end{center}
  are not allowed while 
  \begin{center}
  \HAT \HAT \HAT \HAT $ppppx$  
  \end{center}
  is. This is because it would make sense to follow a chain of pointers, but not to dereference a just referenced variable or reference a just dereferenced one.
  \\Besides, referencing a referenced value would even be an error, since it makes no sense to reference a value.
  
  \item I decided  not to allow pointers to be returned values. This is because we do not have the concept of dynamically allocated heap in \CCC, so there would be no point in returning such a value.
  \\In fact, in the case a pointer was declared inside a function as a local parameter, it would be an error to give it back to the super-routine (since the two stack spaces are different and when a function returns, the stack space used by that function would be no more available), while in the case a pointer was declared outside the function (before the function call) it would be sufficient to pass it as a formal parameter in order to modify it destructively.
  \\I also implemented the pointer parameter passing mechanism, somewhat similar to the parameter passing by reference mechanism.
  
  \item left expression can be pointers or dereferenced pointers.
  \\
  So we can have commands like 
  \begin{center}
  $px := @x;$
  \\\HAT $px := 5;$
  \end{center}
  
  in \CCC and this would also imply that even the value of x is changed to 5.
  
  \item we do not allow pointers arithmetic in \CCC, so expressions like \[px := py + pz\] or whatsoever are not possible.
  \\
  Nevertheless we have two kind of arithmetical expressions wrt pointers: the simple right sided variable in assignments like $px := pz$ (the so called aliasing) and the aforementioned direct access to the stack $px := 0x(12)$. They are considered arithmetical because they are expression in the end, because they are not bound to the pointer semantics itself but just to offset values.
  
  \item since it would have implied too much refactoring of the code, and since pointers in \CCC are simple and are not provided with complex operations, I decided not to make them possible values for array structures (in fact neither arrays selves can be possible values for other arrays).
  \\
  Conversely, there cannot be pointers to vector or matrices structures in \CCC.
  
  \item I heavily avoided to let pointers to functions to exist in \CCC like in \C, that is, pointers cannot have function addresses (or whatever else) as a value, and this is for obvious reasons.
\end{itemize}


  
  
  
  
\subsection{My solution for the problem}
As you can see in \textit{lexer.mll} I added a regular expression in order to recognize direct offsets like 0x$(12)$ and the $NULL$, the new symbols $@$ and \HAT \hspace{2pt} for referencing/dereferencing and the corresponding mappings to the AST through \textit{parser.mly}.
\\There in \textit{parser.mly} I added the new type (of pointers) to the general types.
\\
I also distinguished the assignment of a pointer using the reference symbol $@$. It was a choice done when I began, then it has got there since that time.
\\
As a left expression I also added the dereferencing variable expression, like in \HAT$px := 5;$. Stuff like $px := pz;$ are automagically let allowed by the previous definition of assignment. In fact, the value held by $pz$ is copied into $px$ and it is not important to know whether they are pointers or other kind of variables.
\\
Before I got my hands on the code, the only values a function (or a procedure) could have accepted as formal parameters were those evaluating to \textit{btypes}, so integer and float values. I defined a new production for the actuals instead, including the pointers type also.
\\
Return values have not been modified at all.
\\
\\
As mentioned before, the code is full of comments of mine, so I am not going to point out each modification I did, but only the most important ones.
\\
So for example the \emph{genParam} function in \textit{expressions.ml} takes care of the fact that pointers can be passed as parameters to functions, and it uses the brand new function \emph{genPointerExpr} to do that. This function is very crucial and it is used whenever a variable is tried to be referenced or dereferenced: as its genArithmetical, genBoolean, etc siblings, it affects the intermediate instruction code adding the new instructions.
\\
\\
As a new type for static semantics I introduced \emph{DPointer of stype}, i.e. constructed over another semantic type.
\\So for example when two pointers are used in the same command (assigned for example), their types are compared before everything, taking respect to the two trees (the chains) derived from them.
\\There is a sound exception for this rule, that is when a direct offset is used as an expression. Since there are no means to know the semantic type of a direct offset (not even a human could guess that type), then for semantic type checking I have introduced the \emph{DWhatever} semantic type, meaning "one of the other semantic types". Provided with \emph{DWhatever} two pointer expressions $e1$ $e2$ are evaluated as semantically correct iff

\[e1 = DPointer(st1) \hspace{10pt} \wedge \hspace{10pt} e1 = DPointer(st2) \hspace{10pt} \wedge \] \[(st1 = st2 \hspace{10pt} \vee \hspace{10pt} st1 = DWhatever \hspace{10pt} \vee \hspace{10pt} st2 = DWhatever)\]

.\\In \textit{intermediate.ml} I have modified the instruction set in order to accommodate the introduction of pointers. I added \emph{REF}, \emph{DEREF} and \emph{SETNULL} that behave as their name suggest, then another instruction called \emph{CPY2PT} that is a little more subtle. What it does is to take the input element and copy its value to the destination element only after having it dereferenced.
\\So suppose the first element holds the stack value 0x$(12)$ and we had the instruction (just not correct for sake of explanation)
\[CPY2PT \hspace{10pt} 0x(12) \hspace{10pt} Null \hspace{10pt} 5 \]
then we would set $stack[stack[12]] = 5$ in the \C code.
\\
Note that it could have been achieved the same output by issuing 2 instructions: a \emph{DEREF} and a \emph{CPY}, but I found myself more comfortable this way so I kept it.
\\
The dynamic semantic implementation of all this function is in \textit{target.ml}, of course.
\\
\\
Inside \textit{target.ml} there are the most significant and specific part of the code, in terms of impact on the target code.
\\
The former important new entry is the introduction in the \C code of a null pointer value.
\\Reasoning on the null pointer value, it could not be 0, since 0 represents a valid entry on the stack. It couldn't even be any negative number since it would have found conflicts within procedures and functions (where negative numbers are sound values for offsets for the parameters). So I decided to assign an unreachable offset to it, i.e. -\emph{STACK\_SIZE}-1 (a cell under the maximum number of parameters a function/procedure can be structurally bound to).
\\
Note, out of idle curiosity, that even if \emph{STACK\_SIZE} would be set to \emph{INT\_MAX} for some reason, still my null pointer offset would be a valid integer, since integers are bound between $2^{n-1} - 1$ and $2^{n-1}$.
\\
\\
The automatically generated \C code has been extended letting any offset (seen as an integer value, the index on the stack) to be part of the stack cells or taking the role of a register value.
\\
\\
The code in \textit{target.ml} also deals with invalid pointer dereferencing, and it was one of the most sore point of the whole work. What I eventually did was to apply a function (\emph{check\_invalid\_idx}) to every \C command generated dynamically wrt the \CCC input.
\\
This function takes the string for an instruction and returns that same instruction provided with the invalidity checks for the stack access. So basically it recognizes a string like \emph{stack[ idx ]} and ensures \emph{idx} not to be less than 0.
\\
It was not trivial to me to think up such a function and how make it work correctly. It is there now and it uses the module Str; for this reason the Makefile was modified in order to compile with this new module included.
\\
It has a unique drawback for now: since the function that recognizes strings like \emph{stack[ idx ]} is somewhat poor, it is not able to recognize the indexes for all the possible combinations that might show up. I would even guess that the matching with the index \emph{idx} cannot even be described by a regular grammar, so that as a result it would be necessary to design a more complex parser.
\\
So for this reason I lost the possibility to deal with vectors and matrices in \CCC. They generate errors in the target code.



\section{Extension to Records}
Here it is described how I decided to extend the syntax and the semantics of \CCC in order to allow the use of the new construct of records as described in the assignment paper.


\subsection{Analysis of the problem and solution}
Here I briefly expound the problem and the basic implications over the syntax and the semantics, introducing the solution I gave to solve it.
\\
\\
On this record issue the assignment imposes to define records as

\begin{center}
$type \hspace{3pt} name\_of\_record = record \hspace{5pt} \{$
\\$\hspace{30pt} name\_of\_field1 : type1 ;$
\\$\hspace{30pt} ...$
\\$\hspace{30pt} name\_of\_fieldN : typeN ;$
\\$\hspace{-150pt}\}$
\end{center}

so it looks more like a type definition rather than a record definition.
\\
I decided to provide a basic structure for any kind of type that in future would be created and put at the disposal of the user programmer.
\\
E.g. a new type might be defined as
\[type \hspace{3pt} MyInteger = int\]
in the future; \CCC does not have the means to do that yet, but exploiting the code that I have written it would be quite easy to generate these means.
\\
\\
The introduction of records implies the types of \CCC not to be fixed, and that is a huge difference with the introduction of other constructs like records.
\\
I faced this problem by introducing a new type hash table (carried between functions like it was done the declaration and the procedure hash table).
\\
At declaration time a variable could be claimed to be of type \emph{foobar}. So the system looks up the type table and if she finds it, a type structure is returned. In the case of record (that is the only possible type we can have for the time being) the type structure contains a record tree for \emph{foobar}.
\\
This tree represents the field's structure for the ongoing record. Its leaves are float on integer fields, while the nodes correspond to other records. This was to let previously defined record to be types for fields of other records.

\begin{figure}[htb]
\centering
\includegraphics{record_graph.png}
\end{figure}

Whenever we wanted a variable \emph{foo} of type \emph{foobar} to perform an action we consult the declaration table, that will tell us that \emph{foo} is of type \emph{foobar}. Then we use this information to consult the type table, we get the \emph{foobar} tree and then we can traverse it starting from the offset of the variable.
\\
\\
When \emph{foo} is declared as \emph{foobar} some stack is allocated for her. In the case in question 3 memory cells are allocated (the first for \emph{size}, then for \emph{r} and finally for \emph{i}) and saved into the declaration table (only the first one actually matters, since it defines the position for the whole record, it is similar to the vector stuff).
\\
Inside the declaration table is also inserted an entry that is not actually pushed on the stack, it is only used as a marker (it is the one retrieved when looking up the type table) and it holds the record structure.
\\
\\
Given all this, when $foo.c.r$ is tried to be retrieved, we get the offset of foo on the stack (by looking at the declaration table) and then using the record tree (got from the type table) we skip the first cell (the one for \emph{size}), we find \emph{r} to be in the second memory cell (because it is the second leaf in a pre-order depth first traversal).




\subsection{Implementation details}
Of course, tokens for "record", "type", the dot, the brackets has been added to the lexer. The main \emph{program} production has been extended in the parser to have a list of optional record types to be saved inside the type table and the others to accommodate the introduction of the record variables.
\\
Even the \textit{exception.ml} file has been enhanced with the introduction of two brand new exceptions: NON\_DECLARED\_TYPE (for when looking up the type table) and NON\_DECLARED\_FIELD (when some nonexistent field is tried to be accessed on a user defined type record variable).
\\
\\
The new type table is generated in \textit{main.ml} and passed across almost every function of the front-end. It is filled up by the type definitions at the beginning of the program.
\\
\\
When in expressions or in command a record variable is tried to be used it is retrieved its type from the declaration table, the corresponding tree from the type table and traversed down enough to the requested node/leaf.
\\
In whatever case when a record is involved in some operation (like assignment, comparing, etc.) there is produced a set of instruction, one for each leaf of the record tree, such that every offset of that record is considered properly.
\\
\\
One of the trickiest part of the whole record stuff was about \emph{genRecType} in \emph{declarations.ml}. When we want to do some operations on a record variable, we need to know both (the semantic type and the type structure of that record) and the real offset value of the first occurrence of a variable for that record (so the offset and the actual type of the stored value).
\\
So the first cell on the stack is also assigned to this fictitious element, the record element, that behaves like a marker for the whole record but that is not pushed onto the stack. Both those elements are saved into the declaration table with the same offset value, but different types, bound to the record variable id (like \emph{foo}) and in opposite positions (wrt \emph{Hashtbl} module withdrawal ordering), that is, one as the first element and one as the last one.
\\
When one or the other is tried to be looked up in the declaration table it is possible to choose between the \emph{getVarDeclaration} function (that behaves as before) or the \emph{getVarDeclaration4Semantics} that will return the matching with the record marker for a record variable, and the same value as \emph{getVarDeclaration} for any other variable.
\\
\\
Since the record type deal is mainly handled in the front-end part of \CCC, the extensions to \textit{intermediate.ml} and to \textit{target.ml} are not so worthwhile the discussion and I please you to refer to the code to have more details.


\subsection{What I did not let records do}
Among the great amount of things that could be added to the record type definition and semantics, I did a small portion of them both for my lack of time and for some kind of non trivial hitches between me and the code.
\\
For example, since I introduced records as btypes, they were automatically added to the type of variables that could be returned by a function. However, since \CCC uses the \C functions to implement its functions internally, I did not have any trivial means to let the records be such return values. So I simply cut off this possibility.
\\
\\
For other reasons, records are not supposed to be used as values for arrays, nor for pointers, even if the grammar allow this kind of things [see \textit{testLDL\_29.cre} as an example for this].
\\
I think that for the time being \CCC is a bit incomplete wrt records, they were quite complicated to implement and I am fulfilled just the way I implemented them, keeping them simple, basic but nevertheless sound and wide open towards new enhancements as a matter of software engineering.
\\
\\
As requested, I implemented the comparison operators, but other stuff such as record arithmetic (like issuing $foo + foo$) were not, even if the mechanism would be almost the same (i.e. get the values one after another and relate them "field-wise").
\\
\\
Also for records, I noticed a problem.
\\
It shows up when trying to compare two record values, one of which is a simple [record] variable like \emph{foo}. I got aware of this problem after having all my tests passed, and in order not to impair the code I rather preferred not to touch it any more.
\\
Basically it can be simply solved just in the way I did for variables in assignments for example, it is exactly the same procedure: retrieve the type of the record variable from the declaration table, check for it to be a record, in this case get the corresponding record tree from the type table, traverse it to get the types and the number of leaves and finally access to the stack and consume each field of the record.


\end{document}